package 中等.图.floyd;

/**
 * 有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中
 * edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个
 * 城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。
 * 返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为
 * distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。
 * 注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。
 *
 * @ https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/description/
 * @date 2024/01/03
 */
public class 阈值距离内邻居最少的城市_1334 {

    public static void main(String[] args) {

        System.out.println(findTheCity(4, new int[][]{{0, 1, 3977}, {2, 3, 8807}, {0, 2, 2142}, {1, 3, 1201}}, 8174));

    }

    /**
     * Floyd算法
     * 求出任意两点之间的最短距离
     */
    public static int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][][] dp = new int[n][n][n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 防止加法溢出
                dp[i][j][0] = Integer.MAX_VALUE / 2;
            }
        }
        // 初始化数据，两点直接没有任何点的时候，是直接连接的
        for (int[] edge : edges) {
            int i = edge[0], j = edge[1], w = edge[2];
            // 双向
            dp[i][j][0] = w;
            dp[j][i][0] = w;
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dp[i][j][k + 1] = Math.min(dp[i][j][k], dp[i][k][k] + dp[k][j][k]);
                }
            }
        }

        int[] cnt = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (dp[i][j][n] <= distanceThreshold) {
                    cnt[i]++;
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] <= cnt[ans]) {
                ans = i;
            }
        }
        return ans;
    }

}
